package com.zsj.Tree;


import static com.zsj.Tree.RedBlackTree.Color.BLACK;
import static com.zsj.Tree.RedBlackTree.Color.RED;

/**
 * @author zsj
 * @version 1.0
 * @date 2024/4/21 17:46
 * @description 红黑树
 * 特性:
 * 1.根节点为黑色
 * 2.红色节点不能相邻
 * 3.所有节点有两种颜色 红色与黑色
 * 4.所有null节点为黑色
 * 5.从根到任意一个叶子节点，经过的黑色节点数量一样(黑色完美平衡)
 */
public class RedBlackTree {
    //颜色
    enum Color {
        RED, BLACK;
    }

    //根节点
    private Node root;


    //节点实体
    private static class Node {
        int key;
        Object value;
        Node left;
        Node right;
        Node parent;
        Color color;

        public Node(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        //当前节点是否为左孩子
        boolean isLeftChild() {
            return parent != null && parent.left == this;
        }

        //叔叔节点  (叔叔就是他爹的兄弟)
        Node uncle() {
            //如果这个节点没有父亲 或者没有父亲的父亲 那他肯定没有叔叔节点
            if (parent == null || parent.parent == null) {
                return null;
            }
            //如果有爷爷 看他爹是 是爷爷的右孩子还是左孩子
            //如果为左孩子 那叔叔就是右边的节点
            //反之就是左边的节点
            if (parent.isLeftChild()) {
                //如果父亲是左孩子
                return parent.parent.right;
            }
            return parent.parent.left;
        }

        //兄弟节点
        Node brother() {
            //没有爹你哪里来的兄弟
            if (parent == null) {
                return null;
            }
            //如果当前节点是左孩子 那兄弟就是有孩子
            if (isLeftChild()) {
                return parent.right;
            }
            //否则为左孩子
            return parent.left;
        }
    }


    //判断红
    boolean isRed(Node node) {
        return node != null && node.color == RED;
    }

    //判黑
    boolean isBlack(Node node) {
        return node != null && node.color == BLACK;
    }


    //右旋 1.parent的处理  2.旋转后新增节点的父子关系
    private void rightRotate(Node pink) {
        Node parent = pink.parent;
        Node yellow = pink.left;//需要上升的节点
        Node green = yellow.right;//需要换爹的节点
        if (green != null) {//如果需要换爹的存在
            green.parent = pink;//就把他的爹换成最开始的父节点
        }
        yellow.right = pink;//向上的右节点为最开始的父节点
        yellow.parent = pink.parent;//向上的父亲节点是最开始的父节点
        pink.left = green;//这里也算是重置父子关系
        pink.parent = yellow;//最开始的父节点的父亲设置为它的左节点
        if (parent == null) {
            root = yellow;
        } else if (parent.left == pink) {
            //需要重置以下 最顶层的父亲节点的左右子树关系
            parent.left = yellow;
        } else {
            parent.right = yellow;
        }
    }

    //左旋
    private void leftRotate(Node pink) {
        Node parent = pink.parent;
        Node yellow = pink.right;//需要上升的节点
        Node green = yellow.left;//需要换爹的节点
        if (green != null) {//如果需要换爹的存在
            green.parent = pink;//就把他的爹换成最开始的父节点
        }
        yellow.left = pink;//向上的右节点为最开始的父节点
        yellow.parent = pink.parent;//向上的父亲节点是最开始的父节点
        pink.right = green;//这里也算是重置父子关系
        pink.parent = yellow;//最开始的父节点的父亲设置为它的左节点
        if (parent == null) {
            root = yellow;
        } else if (parent.right == pink) {
            //需要重置以下 最顶层的父亲节点的左右子树关系
            parent.right = yellow;
        } else {
            parent.left = yellow;
        }
    }

    /**
     * 新增或者更新
     *
     * @param key   新增键
     * @param value 新增值
     */
    public void put(int key, Object value) {
        Node p = root;
        Node parent = null;
        while (p != null) {
            parent = p;
            if (key < p.key) {
                //小了往左找
                p = p.left;
            } else if (key > p.key) {
                //大了往右找
                p = p.right;
            } else {
                //如果找到了 就更新
                p.value = value;
            }
        }
        //到这里说明p==null  也就找到了可以插入的地方
        Node inserted = new Node(key, value);
        if (parent == null) {
            //如果父节点为空 说明树是空的  将头节点设置为插入节点
            root = inserted;
        } else if (key < parent.key) {
            parent.left = inserted;//如果插入的key比父亲的小
        } else {
            parent.right = inserted;//比父亲的大
        }
        inserted.parent = parent;
        fixRedRed(inserted);
    }

    /**
     * 因为插入的元素默认都为红色 所以可能会出现红红相邻的情况
     * 不满足红黑树的特性  需要修复
     *
     * @param node 插入节点
     */
    void fixRedRed(Node node) {
        /*
        case1: 插入节点为根节点 将其变黑
        case2: 插入节点的父节点为黑色 则不变
               插入节点的父亲是红色 则促发红红相邻
            case3: 叔叔为红色
            case4: 叔叔为黑色
         */
        if (root == node) {
            root.color = BLACK;//插入节点为根节点 将其变黑
            return;
        }
        if (isBlack(node.parent)) {
            return;//插入节点的父节点为黑色 则不变
        }
        Node parent = node.parent;
        Node uncle = node.uncle();
        Node graParent = parent.parent;
        if (isRed(uncle)) {
            //插入节点的父亲是红色 则促发红红相邻
            if (isRed(node.uncle())) {
                assert uncle != null;
                //如果叔叔也为红色  将叔叔和父亲都变为黑色
                //然后祖父节点变为红色
                //继续对祖父节点进行红红修复
                parent.color = BLACK;
                uncle.color = BLACK;
                graParent.color = RED;
                fixRedRed(graParent);
                return;
            }
        }
        //到这里说明父亲为红 但是叔叔为黑
        /*
            1.父亲为左孩子  插入节点也是左孩子 此时LL不平衡
            2.父亲为左孩子  插入节点是有孩子 此时LR不平衡
            3.父亲为右孩子  插入节点也是右孩子  此时RR不平衡
            4.父亲为右孩子  出入节点是左孩子  此时RL不平衡
             */
        if (parent.isLeftChild() && node.isLeftChild()) {
            //LL
            parent.color = BLACK;
            graParent.color = RED;
            rightRotate(graParent);
        } else if (parent.isLeftChild()) {
            //LR
            leftRotate(parent);
            node.color = BLACK;
            graParent.color = RED;
            rightRotate(graParent);
        } else if (!node.isLeftChild()) {
            //RR
            node.color = BLACK;
            graParent.color = RED;
            leftRotate(graParent);
        } else {
            //RL
            rightRotate(parent);
            node.color = BLACK;
            graParent.color = RED;
            leftRotate(graParent);
        }

    }


    /**
     * 删除
     * 正常删 会用到李代桃僵技巧 遇到黑黑不平衡进行调整
     *
     * @param key 删除键
     */
    public void remove(int key) {
        Node deleted = find(key);
        if (deleted == null) {
            System.out.println("key对应的节点不存在");
            return;
        }
        doRemove(deleted);
    }

    private void doRemove(Node deleted) {
        //需要考虑失衡情况 如果被删除的节点是黑色的 那么红黑树将会失衡
        //如果被删除的节点是红色 红黑树不会失衡
        //删黑色 有一种简单情况 删的是黑 剩下的是红 剩下这个红节点变黑
        Node replace = findReplace(deleted);
        Node parent = deleted.parent;
        if (replace == null) {
            //没有孩子
            if (deleted == root) {
                //case 1:
                //到这里说明删的是根节点且根节点没有孩子 那直接删就可以了
                root = null;
            } else {
                if (isBlack(deleted)) {
                    //复杂情况


                }//红色情况 什么都不用做
                if (deleted.isLeftChild()) {
                    //被删除节点是父亲的左孩子 且被删除节点是叶子节点没有孩子
                    parent.left = null;
                } else {
                    //被删除节点是父亲的右孩子 且被删除节点是叶子节点没有孩子
                    parent.right = null;
                }
                deleted.parent = null;//这里没懂啊？？？
            }
            return;
        }
        if (deleted.left == null || deleted.right == null) {
            //只有一个孩子
            //case 2
            if (deleted == root) {
                //删的是根节点且 根节点只有一个孩子
                //因为能到这里说明 根据红黑树的特性 root的孩子不可能还会有孩子
                //所以我们直接将值转移了就行
                root.key = replace.key;
                root.value = replace.value;
                root.left = null;
                root.right = null;
            } else {
                if (deleted.isLeftChild()) {
                    parent.left = replace;
                } else {
                    parent.right = replace;
                }
                replace.parent = parent;
                deleted.parent = null;
                deleted.left = null;
                deleted.right = null;
                if (isBlack(deleted) && isBlack(replace)) {
                    //如果被删的是黑  且剩下的也是黑

                } else {
                    //case 2
                    replace.color = BLACK;
                }
            }
            return;
        }
        //能到这里说明两个孩子都有
        int t = deleted.key;
        deleted.key = replace.key;
        replace.key = t;

        Object v = deleted.value;
        deleted.value = replace.value;
        replace.value = v;

        //这样一交换 我们就可以把后继节点删掉
        doRemove(replace);
    }

    /**
     * 修复双黑节点
     *
     * @param node 修复节点
     */
    private void fixDoubleBlack(Node node) {

    }

    /**
     * 根据key找寻节点
     *
     * @param key 键
     * @return 节点
     */
    private Node find(int key) {
        Node p = root;
        while (p != null) {
            if (key < p.key) {
                p = p.left;
            } else if (key > p.key) {
                p = p.right;
            } else {
                return p;
            }
        }
        return null;
    }


    //查找剩余节点
    private Node findReplace(Node deleted) {
        if (deleted.left == null && deleted.right == null) {
            //说明被删的节点是叶子节点
            return null;
        }
        if (deleted.left == null) {
            return deleted.right;
        }
        if (deleted.right == null) {
            return deleted.left;
        }
        //到这里说明它两个孩子都在
        Node s = deleted.right;
        while (s.left != null) {
            s = s.left;
        }
        return s;
    }


}
